package quadtree;

import java.util.Vector;

public class NewQuadTreeNode<T> {
	
	/**
	 * Default value for amount of elements
	 */
	protected final static int MAX_ELEMENTS = 2;

	/**
	 * Default value for max depth
	 */
	protected final static int MAX_DEPTH = 4;
	
	public NewQuadTreeNode<T> TopLeft;
	public NewQuadTreeNode<T> TopRight;
	public NewQuadTreeNode<T> BottomLeft;
	public NewQuadTreeNode<T> BottomRight;
	
	protected Vector<NewQuadTreeElement<T>> elements = new Vector<NewQuadTreeElement<T>>();
	
	public DoublePoint startCoordinates;
	public DoubleDimension bounds;
	protected int maxDepth;
	protected int maxElements;
	protected int depth;
	private boolean isDivided;
	
	public NewQuadTreeNode(DoublePoint startCoordinates, DoubleDimension bounds, int depth) {
		this.startCoordinates = startCoordinates;
		this.bounds = bounds;
		this.maxDepth = MAX_DEPTH;
		this.maxElements = MAX_ELEMENTS;
		this.depth = depth;
		isDivided = false;
	}
	
	/**
	 * Returns the node that contains this element
	 * 
	 * @param element
	 * @return
	 */
	protected NewQuadTreeNode<T> findIndex(DoublePoint coordinates) {
		// Compute the sector for the coordinates
		boolean left = (coordinates.x > (startCoordinates.x + bounds.width / 2)) ? false
				: true;
		boolean top = (coordinates.y > (startCoordinates.y + bounds.height / 2)) ? false
				: true;

		// top left
		NewQuadTreeNode<T> tmp = TopLeft;
		if (left) {
			// left side
			if (!top) {
				// bottom left
				tmp = BottomLeft;
			}
		} else {
			// right side
			if (top) {
				// top right
				tmp = TopRight;
			} else {
				// bottom right
				tmp = BottomRight;

			}
		}
		
		return tmp;
	}
	
	/**
	 * Returns all elements for this node
	 * 
	 * @return
	 */
	public Vector<NewQuadTreeElement<T>> getElements() {
		return this.elements;
	}
	
	/**
	 * Returns all elements within the cell that matches the given coordinates
	 * 
	 * @param coordinates
	 * @return
	 */
	public Vector<NewQuadTreeElement<T>> getElements(DoublePoint coordinates) {

		// Check if this node has already been subdivided. Therefore this node
		// should contain no elements
		if (isDivided) {
			return findIndex(coordinates).getElements(coordinates);
		} else {
			return this.elements;
		}
	}
	
	public NewQuadTreeElement<T> getElement(DoublePoint coordinates, T element) {
		if(isDivided) {
			return findIndex(coordinates).getElement(coordinates, element);
		}
		else {
			for(int i = 0; i < elements.size(); i++) {
				if(element.equals(elements.get(i))) {
					return elements.get(i);
				}
			}
			return null;
		}
	}
	
	public boolean removeElement(DoublePoint coordinates, T element) {
		if(isDivided) {
			return findIndex(coordinates).removeElement(coordinates, element);
		}
		else {
			for(int i = 0; i < elements.size(); i++) {
				if(element == elements.get(i).element) {
					elements.remove(i);
				}
			}
			return false;
		}
	}
	
	/**
	 * Insert the element into this node. If needed a subdivision will be
	 * performed
	 * 
	 * @param element
	 */
	public void insert(NewQuadTreeElement<T> element) {
		
		// If this Node has already been subdivided just add the elements to the
		// appropriate cell
		if (isDivided) {
			findIndex(new DoublePoint(element.x, element.y)).insert(element);
			return;
		}

		// Add the element to this node and to parent
		/*if(parent != null) {
			//signifies root node doesnt have a parent
			parent.elements.add(element);
		}*/
		this.elements.add(element);

		// Only subdivide the node if it contain more than MAX_CHILDREN and is
		// not the deepest node
		if (!(this.depth >= maxDepth) && this.elements.size() > maxElements) {
			this.subdivide();

			// Recall insert for each element. This will move all elements of
			// this node into the new nodes at the appropriate cell
			for (int i = 0; i < elements.size(); i++) {
				NewQuadTreeElement<T> current = elements.get(i);
				this.insert(current);
			}
			// Remove all elements from this node since they were moved into
			// subnodes
			this.elements.clear();
		}
	}
	
	public void preDivide() {
		if (!(this.depth >= maxDepth)) {
			this.subdivide();
			TopLeft.preDivide();
			TopRight.preDivide();
			BottomLeft.preDivide();
			BottomRight.preDivide();
		}
	}
	
	/**
	 * Subdivide the current node and add subnodes
	 */
	public void subdivide() {
		
		int depth = this.depth + 1;

		double bx = this.startCoordinates.x;
		double by = this.startCoordinates.y;

		// Create the bounds for the new cell
		DoubleDimension newBounds = new DoubleDimension(this.bounds.width / 2,
				this.bounds.height / 2);

		// Add new bounds to current start coordinates to calculate the new
		// start coordinates
		double newXStartCoordinate = bx + newBounds.width;
		double newYStartCoordinate = by + newBounds.height;

		

		// top left
		TopLeft = new NewQuadTreeNode<T>(new DoublePoint(bx, by), 
				newBounds, depth);

		// top right
		TopRight = new NewQuadTreeNode<T>(new DoublePoint(newXStartCoordinate, by), 
				newBounds, depth);

		// bottom left
		BottomLeft = new NewQuadTreeNode<T>(new DoublePoint(bx, newYStartCoordinate), 
				newBounds, depth);

		// bottom right
		BottomRight = new NewQuadTreeNode<T>(new DoublePoint(newXStartCoordinate, newYStartCoordinate), 
				newBounds, depth);
		isDivided = true;
	}
	
	public Vector<NewQuadTreeElement<T>> queryObject(DoublePoint coordinates, DoubleDimension size) {
		if(!isDivided) {
			return elements;
		}
		else {
			Vector<NewQuadTreeElement<T>> TopLeftList = null;
			Vector<NewQuadTreeElement<T>> BottomLeftList = null;
			Vector<NewQuadTreeElement<T>> BottomRightList = null;
			Vector<NewQuadTreeElement<T>> TopRightList = null;
			Vector<NewQuadTreeElement<T>> master = new Vector<NewQuadTreeElement<T>>();
			if(TopLeft.startCoordinates.x + TopLeft.bounds.width >= coordinates.x
					&& TopLeft.startCoordinates.y + TopLeft.bounds.height >= coordinates.y) {
				//System.out.println("topLeft " + (topLeftNode.startCoordinates.x + topLeftNode.bounds.width) + " >= " + coordinates.x);
				TopLeftList = TopLeft.queryObject(coordinates, size);
			}
			if(TopRight.startCoordinates.x <= coordinates.x + size.width
					&& TopRight.startCoordinates.y + TopRight.bounds.height >= coordinates.y) {
				//System.out.println("topRight " + topRightNode.startCoordinates.x + " <= " + (coordinates.x + size.width));
				TopRightList = TopRight.queryObject(coordinates, size);
			}
			if(BottomLeft.startCoordinates.y <= coordinates.y + size.height
					&& BottomLeft.startCoordinates.x + BottomLeft.bounds.width >= coordinates.x) {
				//System.out.println("bottomLeft " + bottomLeftNode.startCoordinates.y + " <= " + (coordinates.y + size.height));
				BottomLeftList = BottomLeft.queryObject(coordinates, size);
			}
			if(BottomRight.startCoordinates.x <= coordinates.x + size.width
					&& BottomRight.startCoordinates.y <= coordinates.y + size.height) {
				//System.out.println("bottomRight " + bottomRightNode.startCoordinates.x + " <= " + (coordinates.x + size.width)
				//+ " && " + bottomRightNode.startCoordinates.y + " <= " + (coordinates.x + size.height));
				BottomRightList = BottomRight.queryObject(coordinates, size);
			}
			if(TopLeftList != null) {
				master.addAll(TopLeftList);
			}
			if(BottomLeftList != null) {
				master.addAll(BottomLeftList);
			}
			if(BottomRightList != null) {
				master.addAll(BottomRightList);
			}
			if(TopRightList != null) {
				master.addAll(TopRightList);
			}
			return master;
		}	
	}
	
	/**
	 * Clears this node and all subnodes
	 */
	public void clear() {
		if(isDivided) {
			TopLeft.clear();
			TopRight.clear();
			BottomLeft.clear();
			BottomRight.clear();
		}
		elements.clear();
		// top left
		TopLeft = new NewQuadTreeNode<T>(TopLeft.startCoordinates, 
				TopLeft.bounds, depth+1);

		// top right
		TopRight = new NewQuadTreeNode<T>(TopRight.startCoordinates, 
				TopRight.bounds, depth+1);

		// bottom left
		BottomLeft = new NewQuadTreeNode<T>(BottomLeft.startCoordinates, 
				BottomLeft.bounds, depth+1);

		// bottom right
		BottomRight = new NewQuadTreeNode<T>(BottomRight.startCoordinates, 
				BottomRight.bounds, depth+1);
	}
	
	public boolean isDivided() {
		return isDivided;
	}

	/**
	 * Returns the bounds for this Node
	 * 
	 * @return
	 */
	public DoubleDimension getBounds() {
		return this.bounds;
	}

	/**
	 * Returns the startCoordinates for this Node
	 * 
	 * @return
	 */
	public DoublePoint getStartCoordinates() {
		return this.startCoordinates;
	}

	/**
	 * Returns the max elements
	 * 
	 * @return
	 */
	public int getMaxElements() {
		return this.maxElements;
	}

	/**
	 * Returns the depth of this node
	 * 
	 * @return
	 */
	public int getDepth() {
		return this.depth;
	}

	/**
	 * Returns the max depth
	 * 
	 * @return
	 */
	public int getMaxDepth() {
		return this.maxDepth;
	}
}
